Humans can process a tremendous amount of visual and multimedia information. However, they often have difficulty precisely defining and describing such information. For example, it is estimated that the brain can distinguish about 10,000 nuances in colour yet individuals can name only a small number of colour terms (approximately 12). As a consequence, accessing images when searching a database may be challenging using text-based searches which typically use metadata.
Content-based indexing and retrieval methods provide a partial solution to this problem. Emphasis in many content-based retrieval systems is on automated retrieval of relevant items based on notions of similarity to a query item. For example, content-based image retrieval (CBIR) can use features of a selected image of a painting, photograph, print, drawing, or other object to find visually similar images and locate matches in a collection even if they do not share metadata with the original image.
Browsing provides an effective means for exploratory search and a useful alternative to traditional content-based retrieval in which users formulate textual or pictorial queries. In addition, when exploring image and/or multimedia collections, users' intentions might be very vague. They expect the system to be able to provide a variety of cues and options to guide their navigation.
Image and/or multimedia browsing systems need to enable users to visualize collections of items (or their thumbnails or icons) by laying them out appropriately for display. Many systems categorize items into different classes and simply lay them out on a 2D display as 1D lists for each class (Kang, H. and Shneiderman, B. (2000). Visualization methods for personal photo collections browsing and searching in the photofinder. In IEEE International Conference on Multimedia and Expo, pages 1539-1542.). Such 1D lists do not portray well the mutual relationships between items.
Alternatively, 2D map based visualizations (for example, Nguyen, G. and Worring, M. (2006). Interactive access to large image collections using similarity-based visualization. Journal of Visual Languages and Computing, 19(2):203-224) lay out items such that similar items appear close to one another on a 2D display while very different images will be further apart. The 2D map based techniques differ in the manner by which they extract high-dimensional feature vectors from items, measure pair-wise item similarity, and perform dimensionality reduction to map the distribution of items from the high-dimensional space to a 2D display space (Rodden, K. (2002). Evaluating similarity-based visualisations as interfaces for image browsing. PhD thesis, University of Cambridge.).
For example, Rubner et al (Rubner, Y., Tomasi, C., and Guibas, L. (1998). A metric for distributions with applications to image databases. In ICCV, pages 59-66, Bombay, India) used Earth Mover's Distance to measure pair-wise dissimilarity and performed multi-dimensional scaling (MDS) to transform image colour and texture features to a 2D space.
When a large number of items are visualized on a display for browsing, the items will overlap and the extent of this overlap will tend to increase with the number of items. Additionally, regions of the display space will often be empty. These problems are exacerbated by dimensionality reduction techniques that do not consider the sizes of the images used to represent the items (e.g. image thumbnails or icons) when mapping to display positions. Two very similar items will probably be projected to very close positions such that one will be heavily overlapped by the other. In order to reduce overlap, after obtaining image positions on a 2D display by dimensionality reduction, gradient descent methods have been used to move overlapped images towards unoccupied 2D display regions. Basalaj (Basalaj, 2000) and Liu et al. (Liu et al., 2004) used an analogue of MDS in a discrete domain to display each image within a single cell of a grid. While these approaches can help to reduce image overlap, they mainly deal with small numbers of images (about 20˜200).
It is an object of the invention to improve the manner in which items on a display are laid out or arranged.